package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 另一棵树的子树
 * @date 2025/4/16 16:20
 */
public class IsSubtree_572 {

    // TODO 错误解法
    // node不匹配时，往下递归怎么同时保证，既要subRoot从头开始再次匹配，又要分开判断node的左右子树（有任一子树满足即可）

    /**
     * 分析：
     * 判断root中任一节点的任一完整子树，是否与subRoot为相同树。
     * 任一节点包括root节点；完整子树指要到叶子节点，而不是某一部分与subRoot相同就可以。
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot) || dfs(root.left, subRoot) || dfs(root.right, subRoot) ;
    }

    public boolean dfs(TreeNode node, TreeNode subNode) {
        // 都空
        if (node == null && subNode == null) return true;
        // node空，subNode非空
        if (node == null) return false;
        // node空非空，subNode空
        if (subNode == null) return false;
        // node、subNode都非空，且节点值不同
        if (node.val != subNode.val) return false;

        // 节点值相同，node、subNode都向下继续比较
        boolean left = dfs(node.left, subNode.left);
        boolean right = dfs(node.right, subNode.right);

        return left && right;
    }

}
